Thực đơn
Thứ tự yếu
Số thứ tự yếu phân biệt (hoặc là nghiêm ngặt hoặc là tiền thứ tự toàn phần) trên tập có n {\displaystyle n} phần tử nằm có công thức sau (dãy số A000670 trong bảng OEIS):
| Số phần tử | Bất kì | Bắc cầu | Phản xạ | Đối xứng | Tiền thứ tự | Thứ tự bộ phận | Tiền thứ tự toàn phần | Thứ tự toàn phần | Quan hệ tương đương |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
| 2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
| 3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
| 4 | 65536 | 3994 | 4096 | 1024 | 355 | 219 | 75 | 24 | 15 |
| n | 2n2 | 2n2−n | 2n(n+1)/2 | ∑ k = 0 n k ! S ( n , k ) {\textstyle \sum _{k=0}^{n}k!S(n,k)} | n! | ∑ k = 0 n S ( n , k ) {\textstyle \sum _{k=0}^{n}S(n,k)} | |||
| OEIS | A002416 | A006905 | A053763 | A006125 | A000798 | A001035 | A000670 | A000142 | A000110 |
Trong đó S(n, k) là số Stirling loại thứ hai.
Các số này còn được gọi là số Fubini hay số Bell được sắp.
Lấy ví dụ, xét tập chứa ba phần tử khác nhau, có một thứ tự yếu trong đó ba phần tử này ngang nhau. Có ba cách để lấy một tập có một phần tử và một tập chứa hai phần tử còn lại, mỗi trong cách phân hoạch đó sẽ sinh hai thứ tự yếu dựa trên vị trí của tập một phần tử so với tập hai phần tử kia), do đó nhân lại với nhau sinh ra 6 thứ tự yếu dưới dạng đó. Có đúng 1 cách để phân hoạch tập hợp thành ba tập một phần tử, và các tập đó có thể sắp xếp theo 6 cách khác nhau. Do vậy, khi cộng lại sẽ ra 13 thứ tự yếu trên tập ba phần tử khác nhau.
Thực đơn
Thứ tự yếuLiên quan
Tài liệu tham khảo
WikiPedia: Thứ tự yếu